package training.day05;//设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
//
//
// push(x) —— 将元素 x 推入栈中。
// pop() —— 删除栈顶的元素。
// top() —— 获取栈顶元素。
// getMin() —— 检索栈中的最小元素。
//
//
//
//
// 示例:
//
// 输入：
//["MinStack","push","push","push","getMin","pop","top","getMin"]
//[[],[-2],[0],[-3],[],[],[],[]]
//
//输出：
//[null,null,null,null,-3,null,0,-2]
//
//解释：
//MinStack minStack = new MinStack();
//minStack.push(-2);
//minStack.push(0);
//minStack.push(-3);
//minStack.getMin();   --> 返回 -3.
//minStack.pop();
//minStack.top();      --> 返回 0.
//minStack.getMin();   --> 返回 -2.
//
//
//
//
// 提示：
//
//
// pop、top 和 getMin 操作总是在 非空栈 上调用。
//
// Related Topics 栈 设计
// 👍 974 👎 0


import java.util.Arrays;

//leetcode submit region begin(Prohibit modification and deletion)
public class L155 {

    int min = Integer.MAX_VALUE;

    int[] array;

    int size;

    public static void main(String[] args) {
        L155 l155 = new L155();
        l155.push(2);
        l155.push(3);
        l155.push(-4);
//        l155.pop();
        System.out.println(l155.getMin());
    }

    /**
     * initialize your data structure here.
     */
    public L155() {
        array = new int[2];
    }

    public void push(int val) {
        min = Math.min(this.min, val);
        if (size + 1 > array.length) {
            //扩容
            int[] copy = new int[array.length << 1];
            System.arraycopy(array, 0, copy, array.length ,
                    Math.min(array.length, array.length << 1));
            array = copy;
        }
        //加值到顶部
        array[array.length - 1 - size] = val;
        size++;
        //先进先出
    }

    public void pop() {
        //删除，查找最小
        if (min == top()) {
            //一样，比较其他元素，修改min
            if (size == 1) {
                min = Integer.MAX_VALUE;
            } else {
                min = array[array.length + 1 - size];
                for (int i = array.length + 2 - size; i < array.length; i++) {
                    min = Math.min(min, array[i]);
                }
            }
        }
        size--;
    }

    public int top() {
        return array[array.length - size];
    }

    public int getMin() {
        return min;
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */
//leetcode submit region end(Prohibit modification and deletion)
